package com.gxc.linkedList;

import java.util.LinkedList;
import java.util.Stack;

/**
 * 单调栈
 * 在数组中想找到一个数，左边和右边比这个数大、且离这个数最近的位置。
 * 如果对每一个数都想求这样的信息，能不能整体代价达到0(N)
 */
public class MonotoneStack {

    public static void main(String[] args) {
        //                      0 1 2 3 4 5 6 7
        int[] array = new int[]{4,3,5,0,2,1,6,7};

        int[][] result = findNearBiggerNoRepeat(array);
        for (int i = 0; i < result.length; i++) {
            System.out.println("");
            for (int j = 0; j < result[i].length; j++) {
                System.out.print(result[i][j] + " ");
            }
        }

        //                       0 1 2 3 4 5 6 7
        int[] array2 = new int[]{4,3,5,4,3,3,6,7};
        result = findNearBiggerWithRepeat(array);
        for (int i = 0; i < result.length; i++) {
            System.out.println("");
            for (int j = 0; j < result[i].length; j++) {
                System.out.print(result[i][j] + " ");
            }
        }
    }

    /**
     * 数组有重复数据
     * @param array
     * @return
     */
    private static int[][] findNearBiggerWithRepeat(int[] array) {
        if (array == null || array.length ==0) return null;
        //相同大小的元素压入一个链表内
        Stack<LinkedList<Integer>> monotoneStack = new Stack<>();

        int[][] result = new int[array.length][2];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                result[i][j] = -1;
            }
        }

        int cur = -1;
        for (int i = 0; i < array.length; i++) {
            if (monotoneStack.isEmpty()) {
                LinkedList<Integer> list = new LinkedList();
                list.addLast(i);
                monotoneStack.push(list);
            } else {
                while (!monotoneStack.isEmpty()) {
                    LinkedList<Integer> peek = monotoneStack.peek();
                    if (array[peek.peekFirst()]<array[i]) {
                        peek = monotoneStack.pop();
                        for (int j = 0; j < peek.size(); j++) {
                            cur = peek.pollFirst();
                            result[cur][1] = i;
                            if (!monotoneStack.isEmpty()) {
                                result[cur][0] = monotoneStack.peek().peekLast();
                            }
                        }
                    } else if (array[peek.peekFirst()]==array[i]) {
                        peek.addLast(i);
                        break;
                    } else {
                        LinkedList<Integer> list = new LinkedList();
                        list.addLast(i);
                        monotoneStack.push(list);
                        break;
                    }
                }
            }
        }

        return result;
    }

    /**
     * 数组无重复数据
     * @param array
     * @return
     */
    private static int[][] findNearBiggerNoRepeat(int[] array) {
        if (array == null || array.length ==0) return null;
        Stack<Integer> monotoneStack = new Stack<>();

        int[][] result = new int[array.length][2];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                result[i][j] = -1;
            }
        }

        int cur = -1;
        for (int i = 0; i < array.length; i++) {
            //比较栈顶的的元素小于当前的元素，弹出栈顶元素，并记录元素的信息,
            //如果栈顶的的元素大于当前的元素，当前元素直接加入栈
            //当前i就是右侧最近比栈顶大的，栈顶下的元素就是左侧最近比栈顶大的
            //保持栈的单调性，栈顶小，栈底大
            while (!monotoneStack.isEmpty()) {
                if (array[monotoneStack.peek()] < array[i]) {
                    cur = monotoneStack.pop();
                    result[cur][1] = i;
                    if (!monotoneStack.isEmpty()) {
                        result[cur][0] = monotoneStack.peek();
                    }
                } else {
                    break;
                }
            }
            monotoneStack.push(i);
        }
        //当数组循环完，栈已从小到大有序
        while (!monotoneStack.isEmpty()) {
            cur = monotoneStack.pop();
            if (!monotoneStack.isEmpty()) {
                result[cur][0] = monotoneStack.peek();
            }
        }
        return result;
    }


}
